package io.zouyalong.algo.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/generate-parentheses/
 */

public class GenerateParentheses {
    public static void main(String[] args) {
        var inst = new GenerateParentheses();
        var result = inst.solution1(3);
        GenerateParentheses.printList(result);
    }

    public static void printList(List<String> src) {
        for (String s : src) {
            System.out.printf("%s\n", s);
        }
    }

    public List<String> solution1(int n) {
        var res = new LinkedList<String>();
        var builder = new StringBuilder(2*n);
        backtrace(n, n, res, builder);
        return res;
    }

    private void backtrace(int validLeft, int validRight, List<String> res, StringBuilder str) {
        if (validLeft == 0 && validRight == 0) {
            res.add(str.toString());
            return;
        }
        if (validLeft > 0) {
            str.append('(');
            backtrace(validLeft - 1, validRight, res, str);
            str.deleteCharAt(str.length() - 1);
        }
        if (validRight > validLeft) {
            str.append(')');
            backtrace(validLeft, validRight - 1, res, str);
            str.deleteCharAt(str.length() - 1);
        }
    }
}
